Functional approximation circuits, such as reciprocal approximation circuits, are known in the art. For example, a division (e.g., in 2D and 3D graphics implementations) is typically implemented using a reciprocal approximation circuit. The resulting reciprocal approximation of the divisor is multiplied with the dividend, thereby emulating the divide operation.
A conventional reciprocal approximation circuit uses an iterative method (e.g., the Newton-Raphson method) based on an initial estimate. Reciprocal approximations are fed back through the circuit until a reciprocal approximation of a desired precision is obtained. This iterative process takes significant time. Thus, a faster circuit and method for approximating, for example, a reciprocal are desired.
An approximation circuit approximates a function f(x), given an input value xe2x80x9cxxe2x80x9d, by computing and adding at least the first two terms in a Taylor series (i.e., f(a) and fxe2x80x2(a)(xxe2x88x92a)) where xe2x80x9caxe2x80x9d is an approximation value reasonably close to the input value xe2x80x9cxxe2x80x9d. For example, xe2x80x9caxe2x80x9d may share the most significant bits of input value xe2x80x9cxxe2x80x9d. The values f(a) and fxe2x80x2(a) can be provided by look-up tables. A first look-up table receives the approximation value xe2x80x9caxe2x80x9d, and provides a function f(a). Similarly, a second look-up table receives the approximation value xe2x80x9caxe2x80x9d and provides a first derivative fxe2x80x2(a) of the function f(a). A multiplier then multiplies the value fxe2x80x2(a) represented by the bits generated by the second look-up table by a difference (xxe2x88x92a) between value xe2x80x9cxxe2x80x9d and value xe2x80x9caxe2x80x9d. An adder adds the first term represented by the bits generated by the first look-up table and the second term represented by the bits generated by the multiplier to provide an approximation of f(x).
In one embodiment, the third term (i.e., (xc2xd)fxe2x80x3(a)(xxe2x88x92a)2) of the Taylor series is also computed. For example, a third look-up table receives the approximation value xe2x80x9caxe2x80x9d and provides a value of one half of the second derivative (xc2xd)fxe2x80x3(a) of the function f(a). A fast squaring circuit receives the difference (xxe2x88x92a) and generates bits representing the square (xxe2x88x92a)2. Another multiplier receives the value (xc2xd)fxe2x80x3(a) and the value (xxe2x88x92a)2 to generate the third term (xc2xd)fxe2x80x3(a)(xxe2x88x92a)2.
Since the terms of the Taylor series are computed in parallel, an adder adds all the terms simultaneously to obtain the approximation. Since no iteration is performed, the approximation circuit of the present invention is faster than conventional approximation circuits.